/***************************************************************************************
* Copyright (c) 2014-2022 Zihao Yu, Nanjing University
*
* NEMU is licensed under Mulan PSL v2.
* You can use this software according to the terms and conditions of the Mulan PSL v2.
* You may obtain a copy of Mulan PSL v2 at:
*          http://license.coscl.org.cn/MulanPSL2
*
* THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS, WITHOUT WARRANTIES OF ANY KIND,
* EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO NON-INFRINGEMENT,
* MERCHANTABILITY OR FIT FOR A PARTICULAR PURPOSE.
*
* See the Mulan PSL v2 for more details.
***************************************************************************************/

#include <isa.h>
#include <memory/paddr.h>
/* We use the POSIX regex functions to process regular expressions.
 * Type 'man regex' for more information about POSIX regex functions.
 */
#include <regex.h>

enum {
  TK_NOTYPE = 256, TK_EQ,TK_NUM,TK_NEQ,TK_AND,
  TK_HEX,TK_REG,TK_DEREF,
  /* TODO: Add more token types */

};

static struct rule {
  const char *regex;
  int token_type;
} rules[] = {

  /* TODO: Add more rules.
   * Pay attention to the precedence level of different rules.
   */

  {" +", TK_NOTYPE},    // spaces
  {"0x[0-9a-fA-F]+",TK_HEX},  // hex
  {"[0-9]+", TK_NUM},   // num
  {"\\(", '('},         // left parentheses
  {"\\*", '*'},         // mutiply
  {"\\/", '/'},         // division      
  {"\\+", '+'},         // plus
  {"\\-", '-'},         // minus
  {"==", TK_EQ},        // equal
  {"\\)", ')'},         // right parnetheses
  {"!=",TK_NEQ},        // not equal
  {"&&",TK_AND},        // and
  {"\\$[a-zA-Z0-9_]+",TK_REG} // reg
};

#define NR_REGEX ARRLEN(rules)

static regex_t re[NR_REGEX] = {};

/* Rules are used for many times.
 * Therefore we compile them only once before any usage.
 */
void init_regex() {
  int i;
  char error_msg[128];
  int ret;

  for (i = 0; i < NR_REGEX; i ++) {
    ret = regcomp(&re[i], rules[i].regex, REG_EXTENDED);
    if (ret != 0) {
      regerror(ret, &re[i], error_msg, 128);
      panic("regex compilation failed: %s\n%s", error_msg, rules[i].regex);
    }
  }
}

typedef struct token {
  int type;
  char str[32];
} Token;

static Token tokens[1024] __attribute__((used)) = {};
static int nr_token __attribute__((used))  = 0;

static bool make_token(char *e) {
  int position = 0;
  int i;
  regmatch_t pmatch;

  nr_token = 0;

  while (e[position] != '\0') {
    /* Try all rules one by one. */
    for (i = 0; i < NR_REGEX; i ++) {
      if (regexec(&re[i], e + position, 1, &pmatch, 0) == 0 && pmatch.rm_so == 0) {
        char *substr_start = e + position;
        int substr_len = pmatch.rm_eo;

        Log("match rules[%d] = \"%s\" at position %d with len %d: %.*s",
            i, rules[i].regex, position, substr_len, substr_len, substr_start);

        position += substr_len;

        /* TODO: Now a new token is recognized with rules[i]. Add codes
         * to record the token in the array `tokens'. For certain types
         * of tokens, some extra actions should be performed.
         */
        
        switch (rules[i].token_type) {
          case '(':
            tokens[nr_token].type = '(';
            nr_token++;
            break;
          case '*':
            tokens[nr_token].type = '*';
            nr_token++;
            break;
          case '/':
            tokens[nr_token].type = '/';
            nr_token++;
            break;
          case '+':
            tokens[nr_token].type = '+';
            nr_token++;
            break;
          case '-':
            tokens[nr_token].type = '-';
            nr_token++;
            break;
          case ')':
            tokens[nr_token].type = ')';
            nr_token++;
            break;
          case TK_EQ:
            tokens[nr_token].type = TK_EQ;
            nr_token++;
            break;
          case TK_NEQ:
            tokens[nr_token].type = TK_NEQ;
            nr_token++;
            break; 
          case TK_AND:
            tokens[nr_token].type = TK_AND;
            nr_token++;
            break; 
          case TK_HEX:
            tokens[nr_token].type = TK_HEX;
            strncpy(tokens[nr_token].str, substr_start+2, substr_len-2);
            tokens[nr_token].str[substr_len-2] = '\0';
            nr_token++;
            break; 
          case TK_REG:
            tokens[nr_token].type = TK_REG;
            strncpy(tokens[nr_token].str, substr_start+1, substr_len-1);
            tokens[nr_token].str[substr_len-1] = '\0';
            nr_token++;
            break; 
          case TK_DEREF:
            tokens[nr_token].type = TK_DEREF;
            strncpy(tokens[nr_token].str, substr_start+1, substr_len-1);
            tokens[nr_token].str[substr_len-1] = '\0';
            nr_token++;
            break; 
          case TK_NUM:
            tokens[nr_token].type = TK_NUM;
            strncpy(tokens[nr_token].str, substr_start, substr_len);
            tokens[nr_token].str[substr_len] = '\0';
            nr_token++;
          default: ;
        }

        break;
      }
    }

    if (i == NR_REGEX) {
      printf("no match at position %d\n%s\n%*.s^\n", position, e, position, "");
      return false;
    }
  }

  return true;
}

bool check_parentheses(int p, int q){
  if(p==q){
    return true;
  }
  if (tokens[p].type == '(' && tokens[q].type == ')'){
    int left = 0;
    int right = 0;
    for (int i = p+1; i <= q-1; i ++){
      if (tokens[i].type == '('){
        left ++;
      }
      if (tokens[i].type == ')'){
        right ++;
      }
      if (left < right){
        return false;   // the number of left must greater than right
      }
    }
    if( left != right){
      return false;
    }
    return true;
  }
  return false;
}

int eval(int p, int q){
  if (p > q){
    assert(0);
  }
  else if (p == q){
    if(tokens[p].type == TK_NUM){
      return atoi(tokens[p].str);
    }
    else if(tokens[p].type == TK_HEX){
      int num;
      sscanf(tokens[p].str,"%x",&num);
      return num;
    }
    else if(tokens[p].type == TK_REG){
      bool success = NULL;
      int res = isa_reg_str2val(tokens[p].str,&success);  // word_t -> int
      if(success){
        return res;
      }else{
        assert(0);
      }
    }
  }
  else if (check_parentheses(p,q) == true){
    return eval(p + 1, q - 1);
  }
  else if(tokens[p].type == TK_DEREF){
    int addr  = eval(p+1,q);
    uint32_t val = paddr_read(addr,1);
    return val;
  }
  else {
    int op = 0;
    int is_in = 0;
    for(int i = p; i <= q; i ++){
      if (tokens[i].type == '('){
        is_in++;
      }
      if (tokens[i].type == ')'){
        is_in--;
      }
      if ((tokens[i].type == '+' || tokens[i].type == '-' || tokens[i].type == '*' || tokens[i].type == '/')&&is_in==0){
        if (op == 0){
          op = i;     // first time change the operator position
        }
        else {
          if (tokens[i].type == '*' || tokens[i].type == '/'){
            if (tokens[op].type == '*' || tokens[op].type == '/'){
                op = i;
              }
          }
          else {
            // the priority of + and - is the lowest
            if (tokens[i].type == '+' || tokens[i].type == '-'){
              op  = i;
            }
          }
        }
        
      }

    }
    Log("The op is %c",tokens[op].type);
    if(!(tokens[op].type == '+' || tokens[op].type == '-' || tokens[op].type == '*' || tokens[op].type == '/')){
      assert(0);
    }
    assert(op-1>=p);
    assert(op+1<=q);
    int val1 = eval(p, op - 1);
    int val2 = eval(op + 1, q);
    switch (tokens[op].type){
      case '+' : return val1 + val2;
      case '-' : return val1 - val2;
      case '*' : return val1 * val2;
      case '/' : return val1 / val2;
      default: assert(0);
    }
  }
  return 0;
}

word_t expr(char *e, bool *success) {
  if (!make_token(e)) {
    *success = false;
    return 0;
  }
  // for(int i=0;i<nr_token-1;i++){
  //   Log("The op list %d is %c",i,tokens[i].type);
  // }
  /* TODO: Insert codes to evaluate the expression. */
  // TODO();
  for(int i=0;i< nr_token;i++){
    if(tokens[i].type == '*' && (i==0 || (tokens[i-1].type != TK_NUM && tokens[i-1].type != TK_HEX && 
    tokens[i-1].type != TK_REG && tokens[i-1].type != '(' &&tokens[i-1].type != ')'))){
      tokens[i].type = TK_DEREF;
    }
  }
  
  unsigned val = eval(0, nr_token-1);
  *success = true;
  return val;
}
